#include "text.hpp"
#include <list>
#include <vector>
#include <cctype>
#include <algorithm>

namespace vl
{

namespace
{
	typedef std::string::size_type size_type; 
	
	size_t minimum(size_type a, size_type b, size_type c)
	{
		size_type min = a;
		if(b < min)
			min = b;
		if(c < min)
			min = c;
		return min;
	}
}

bool istrCmp( std::string const& a, std::string const & b )
{
	std::string::const_iterator itA, itB;
	
	for (itA = a.begin(), itB = b.begin();
		    itA != a.end() && itB != b.end();
		    ++itA, ++itB)
	{
		char ca = std::toupper(*itA);
		char cb = std::toupper(*itB);
		if(ca != cb)
			return false;
	}
	
	return (itA == a.end() && itB == b.end());
}

bool iisPrefixOfOther(
	std::string::const_iterator a,
	std::string::const_iterator ae,
	std::string::const_iterator b,
	std::string::const_iterator be
)
{
	for (; a != ae && b != be;
		    ++a, ++b)
	{
		char ca = std::toupper(*a);
		char cb = std::toupper(*b);
		if(ca != cb)
			return false;
	}
	return true;
}

std::size_t levenshtein_distance(std::string const& a, std::string const& b)
{
	if(a == b)
		return 0;

	// n = alen, m = blen
	size_type alen = a.size();
	size_type blen = b.size();
	
	if(alen && blen)
	{
		++alen; ++blen;
		size_type* d = new size_type[alen * blen];
		
		for(size_type k = 0; k < alen; ++k)
			d[k] = k;
		
		for(size_type k = 0; k < blen; ++k)
			d[k * alen] = k;
			
		for(size_type i = 1; i < alen; ++i)
		for(size_type j = 1; j < blen; ++j)
		{
			size_type cost = (tolower(a[i - 1]) == tolower(b[j - 1])) ? 0 : 1;

        	d[j*alen + i] = minimum(
				d[(j - 1)*alen + i] + 1,
				d[j*alen + i - 1] + 1,
				d[(j - 1)*alen + i - 1] + cost
			);
		}
		size_type distance = d[alen*blen - 1];
		delete[] d;
		return distance;
	}
	else
		return std::max(alen, blen);
}

std::size_t lcsubstr_sum(std::string const& a, std::string const& b)
{
	std::vector<size_type> L((b.size() + 1) * 2);
	
	size_type* lastL = &L[0];
	size_type* curL = &L[b.size() + 1];
	
	size_type count = 0;
	size_type z = 0;
	
	for(size_type i = 0; i < a.size(); ++i)
	{
		std::fill(curL, curL + b.size() + 1, 0);
		
		for(size_type j = 0; j < b.size(); ++j)
		{
			if(a[i] == b[j])
			{
				size_type cand = lastL[j] + 1;
				
				curL[j + 1] = cand;
				
				if(cand > z)
				{
					z = cand;
					count = 1;
				}
				else if(cand == z)
				{
					++count;
				}
			}
		}
		
		std::swap(curL, lastL);
	}
	
	return z;
}


std::size_t lcsubseq(std::string const& a, std::string const& b)
{
	std::vector<size_type> L((b.size() + 1) * 2);
	
	size_type* lastL = &L[0];
	size_type* curL = &L[b.size() + 1];
	
	size_type count = 0;
	size_type z = 0;
	
	for(size_type i = 0; i < a.size(); ++i)
	{
		//std::fill(curL, curL + b.size() + 1, 0);
		curL[0] = 0;
		
		for(size_type j = 0; j < b.size(); ++j)
		{
			if(a[i] == b[j])
			{
				size_type cand = lastL[j] + 1;
				
				curL[j + 1] = cand;
			}
			else
			{
				if(lastL[j + 1] > curL[j])
				{
					curL[j + 1] = lastL[j + 1];
				}
				else
				{
					curL[j + 1] = curL[j];
				}
			}
		}
		
		std::swap(curL, lastL);
	}
	
	return lastL[b.size()];
}

void replace_all(std::string& str, std::string const& source, std::string const& dest)
{
	std::string::size_type start = str.find(source);
	
	while(start != std::string::npos)
	{
		str.replace(start, source.size(), dest);
		start = str.find(source, start + dest.size());
	}
}

void trim(std::string& str)
{
	std::size_t b = 0;
	
	while(b < str.size() && std::isspace((unsigned char)str[b]))
		++b;
	
	std::size_t e = str.size();
		
	while(b < e && std::isspace((unsigned char)str[e - 1]))
		--e;
		
	str = str.substr(b, e - b);
}

bool shell_complete_common(
	std::string& s,
	std::string::const_iterator b,
	std::string::const_iterator e,
	SortedListT::const_iterator& firstMatch,
	SortedListT::const_iterator& lastMatch,
	SortedListT const& sortedList)
{
	SortedListT::const_iterator item = sortedList.lower_bound( s );
	
	size_t len = s.size();
	
	if( item == sortedList.end() )
		return false;
		
	if ( ! iisPrefixOfOther( b, e, item->begin(), item->end()) )
		return false;

	firstMatch = item;
		
	while ( item != sortedList.end() && iisPrefixOfOther( b, e, item->begin(), item->end()) )
	{
		lastMatch = item;
		item++;
	}
	
	if (lastMatch == firstMatch)
	{
		s = *firstMatch + ' ';
		return false;
	}
	else
	{
		lastMatch++;
		bool differenceFound = false;
		size_t i = len;
		for(; ; ++i)
		{
			for (item = firstMatch; item != lastMatch; ++item)
			{
				if(item->size() <= i
				|| tolower((*item)[i]) != tolower((*firstMatch)[i]))
				{
					differenceFound = true;
					break;
				}
			}
			
			if(differenceFound)
				break;
		}
		
		s = std::string(firstMatch->begin(), firstMatch->begin() + i);
		
		if(i == len)
			return true;
	}
	
	return false;
}

bool portable_getline(std::istream& str, std::string& s)
{
	std::string l;
	
	for(int len = 0; ; ++len)
	{
		int c = str.get();
		if(c == std::istream::traits_type::eof())
		{
			if(len == 0)
				return false;
			s = l;
			return true;
		}
		
		if(c == '\r' || c == '\n')
		{
			if(len == 0) // Skip zero length lines
			{
				--len;
			}
			else
			{
				s = l;
				return true;
			}
		}
		else
			l += (char)c;
	}
}

}

